package com.ntd.study.algorithm.sort;

import cn.hutool.aop.ProxyUtil;
import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;
import com.ntd.study.algorithm.sort.impl.*;
import com.ntd.study.modular.hutool.proxy.TimeIntervalAspect;
import ntd.util.UtilLog;
import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiFunction;

/**
 * 算法详解
 * 时间复杂度 - 函数，它定性描述了该算法的运行时间
 * 常数阶 - 执行运算一次 - O(1)
 * 线性阶 - 执行运算n次 - O（n）
 * 平方阶 - 执行运算n*n次 - O（n*n）
 *
 * 深度优先：对每一个可能的分支路径深入到不能深入为止，每个节点只能访问一次 - 二叉树的深度优先特殊：先序遍历、中序遍历、后序遍历
 * 广度优先：从上往下对每一层依次访问，在每一层中，从左往右依次进行遍历
 *
 * 直接插入排序算法 -
 * 希尔排序算法 -
 *
 */
public class SortAlgorithm {

    BiFunction<Integer, Integer, Boolean> sortRule = (Integer a, Integer b) -> a > b;

    private List<SortBO<Integer>> sorts = new ArrayList() {{
        add(new SortBO(new SortSelect(), "选择排序"));
        add(new SortBO(new SortBubbling(), "冒泡排序"));
        add(new SortBO(new SortInsert(), "插入排序"));
        add(new SortBO(new SortHill(), "希尔排序"));
        add(new SortBO(new SortMerge(), "归并排序"));
        add(new SortBO(new SortFast(), "快速排序"));
        add(new SortBO(new SortHeap(), "堆排序"));
        add(new SortBO(new SortCount(), "计数"));
    }};

    public static void main(String[] args) {
        new SortAlgorithm().extracted();
    }

    private void extracted() {
        Integer[] randomIntegerArray = randomIntegerArray(10000);
        sorts.forEach(sortBO -> {
            Sort<Integer> sortProxy = getSortProxy(sortBO);
            Integer[] sort = sortProxy.sort(ArrayUtil.clone(randomIntegerArray), sortRule);
            UtilLog.info(sortBO.getName(), ArrayUtil.join(sort, "-"));
        });
    }

    /**
     * 获取代理对象
     *
     * @param sortBO
     * @return
     */
    private static Sort getSortProxy(SortBO<Integer> sortBO) {
        return ProxyUtil.proxy(sortBO.getSort(), TimeIntervalAspect.class);
    }

    /**
     * 随机生成数组
     * @param limit
     * @return
     */
    private Integer[] randomIntegerArray(int limit) {
        List<Integer> integerList = new ArrayList<>();
        for (int i = 0; i < limit; i++) {
            integerList.add(RandomUtil.randomInt(100000));
        }
        return integerList.toArray(new Integer[]{});
    }

    @Data
    static class SortBO<T> {
        Sort<T> sort;
        String name;

        public SortBO() {
        }

        public SortBO(Sort<T> sort, String name) {
            this.sort = sort;
            this.name = name;
        }
    }
}
